/*
题目链接：https://leetcode.cn/problems/kth-missing-positive-number/description/
题目：1539.第k个缺失的正整数
提交时间：2024.9.9
二分
*/

//理解官方题解所得：
class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        if(arr[0]>k) return k;         //说明第k个数在arr[0]前面，从第一位算起，则返回k本身
        int l=0,r=arr.size();
        while(l<r){                   //由下标i和此下标数arr[i]之前缺失的数量关系num[i]为：arr[i]-i-1
            int mid=l+(r-l)/2;         //则找第k个缺失的数=找num[i-1]<k<=num[i]--->则数为：k-num[i-1]+arr[i-1]
            int x=0;
            if(mid<arr.size()){       //检查该下标是否会超数组值下标
                x=arr[mid];        
            }
            else{
                x=100000;     //如果超出范围，为了让二分能找到结果，则将最后一个值赋值为最大值，此时不会影响答案
            }
            if(x-mid-1>=k) r=mid;      //找到前面缺失的几位
            else l=mid+1;                         
        }
        return k-(arr[r-1]-(r-1)-1)+arr[r-1];
    }
};

//自己解法，枚举
class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        vector<int>num;
        map<int,int>a;
        for(int i=0;i<arr.size();i++){
            a[arr[i]]++;
        }
        int m=arr[arr.size()-1];     //表示最后一个数据
        for(int i=1;i<=m;i++){
            if(a[i]==0) {
                num.push_back(i);
                k--;
            }
            if(k==0) break;
        }
        if(k!=0){          //说明还没有到达要找的数
            num.push_back(m+k);
        }
        return num[num.size()-1];
    }
};